

//在二维网格 grid 上，有 4 种类型的方格： 
//
// 
// 1 表示起始方格。且只有一个起始方格。 
// 2 表示结束方格，且只有一个结束方格。 
// 0 表示我们可以走过的空方格。 
// -1 表示我们无法跨越的障碍。 
// 
//
// 返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。 
//
// 每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。 
//
// 
//
// 示例 1： 
//
// 输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
//输出：2
//解释：我们有以下两条路径：
//1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
//2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2) 
//
// 示例 2： 
//
// 输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
//输出：4
//解释：我们有以下四条路径： 
//1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
//2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
//3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
//4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3) 
//
// 示例 3： 
//
// 输入：[[0,1],[2,0]]
//输出：0
//解释：
//没有一条路能完全穿过每一个空的方格一次。
//请注意，起始和结束方格可以位于网格中的任意位置。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= grid.length * grid[0].length <= 20
// 
// Related Topics 位运算 数组 回溯 矩阵 👍 192 👎 0


package cn.db117.leetcode.solution9;

/**
 * 980.不同路径 III.unique-paths-iii
 *
 * @author db117
 * @since 2022-04-02 11:42:56
 **/

public class Solution_980 {
    public static void main(String[] args) {
        Solution solution = new Solution_980().new Solution();

        System.out.println(solution.uniquePathsIII(new int[][]{{1, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 2, -1}}));
        // [[0,0,0,0,0,0,2,0,0,0],[0,0,0,0,0,0,0,0,1,0]]
        // 1
        solution = new Solution_980().new Solution();
        System.out.println(solution.uniquePathsIII(new int[][]{{0, 0, 0, 0, 0, 0, 2, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 1, 0}}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        int ans;
        // 1 的数量
        int count;
        int[][] arr = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        public int uniquePathsIII(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            // 标记是否可通行
            boolean[][] flag = new boolean[m][n];
            // 开始位置
            int startRow = -1;
            int startCol = -1;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int num = grid[i][j];
                    if (num == 0) {
                        count++;
                    }
                    if (num == -1) {
                        flag[i][j] = true;
                    }
                    if (num == 1) {
                        flag[i][j] = true;
                        startRow = i;
                        startCol = j;
                    }
                }
            }

            // 深度优先
            dfs(grid, startRow, startCol, flag, 0);
            return ans;
        }

        private void dfs(int[][] grid, int row, int col, boolean[][] flag, int cur) {

            if (grid[row][col] == 2) {
                if (cur == count + 1) {
                    ans++;
                }
                return;
            }

            for (int[] dict : arr) {
                int r = row + dict[0];
                int c = col + dict[1];
                if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
                    continue;
                }
                if (flag[r][c]) {
                    continue;
                }

                flag[r][c] = true;
                dfs(grid, r, c, flag, cur + 1);
                flag[r][c] = false;
            }

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}